
/*
回溯
连接：https://leetcode.cn/problems/path-with-maximum-gold/description/
题目：  黄金矿工

枚举矩阵中所有的位置当成起点，来⼀次深度优先遍历，统计出所有情况下能收集到的⻩⾦数的最⼤
值即可。

   
    
*/
class Solution {
public:
    bool vis[16][16];
    int ret;
    int m,n;
    int r[4] = {0,0,-1,1};
    int c[4] = {-1,1,0,0};
    int getMaximumGold(vector<vector<int>>& grid) {
        m=grid.size();
        n=grid[0].size();
        for(int i =0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]!=0)
                {
                    vis[i][j]=true;
                    dfs(grid,i,j,grid[i][j]);
                    vis[i][j] = false;
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<int>>& grid,int i,int j,int sum)
    {
        if(grid[i][j]==0)
        {    
            ret = max(ret,sum);
            return ;
        }
        for(int k=0;k<4;k++)
        {
            int x = i+r[k];
            int y = j+c[k];
            if(x>=0 && x<m && y>=0 && y<n && !vis[x][y])
            {
                vis[x][y] = true;
                dfs(grid,x,y,sum+grid[x][y]);
                vis[x][y] = false;
            }
        }
        //全部都找完了
        ret =  max(ret,sum);
    }
};